#include <vector>
#include <stack>
#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;

        TreeNode* cur = root;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            ans.push_back(top->val);
            cur = top->right;
        }

        return ans;
    }
};

///////////////////////////

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* prev = nullptr;

        TreeNode* cur = root;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            if (top->right == nullptr || top->right == prev)
            {
                st.pop();
                ans.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }

        return ans;
    }
};

//////////////////////////////////////////////////
#include <queue>

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> q;

        for (int i = 0; i < gifts.size(); i++)
        {
            q.push(gifts[i]);
        }

        while (k--)
        {
            int top = q.top();
            q.pop();

            top = sqrt((double)top);
            q.push(top);
        }

        long long sum = 0;
        while (!q.empty())
        {
            sum += q.top();
            q.pop();
        }
        return sum;
    }
};